package com.fh.twopointers;

/**
 * 19. 删除链表的倒数第 N 个结点
 * @author fuhao
 * @date 2025/10/14 22:20
 */
public class T19RemoveNthFromEnd {

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            // 同样使用虚拟头节点简化操作
            ListNode dummy = new ListNode(0, head);
            int length = 0;

            // 第一次遍历：计算链表总长度
            ListNode current = head;
            while (current != null) {
                length++;
                current = current.next;
            }

            // 找到倒数第n个节点的前一个节点（即第L-n个节点）
            current = dummy;
            for (int i = 0; i < length - n; i++) {
                current = current.next;
            }

            // 删除节点
            current.next = current.next.next;

            return dummy.next;
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
